\documentclass[a4paper,10pt]{article}
\usepackage[paper=a4paper, hmargin=1.5cm, bottom=1.5cm, top=3.5cm]{geometry}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[spanish]{babel}
\usepackage{xspace}
\usepackage{xargs}
\usepackage{ifthen}
\usepackage{aed2-tad,aed2-symb,aed2-itef}
\usepackage{listings}


\newcommand{\moduloNombre}[1]{\textbf{#1}}

\let\NombreFuncion=\textsc
\let\TipoVariable=\texttt
\let\ModificadorArgumento=\textbf
\newcommand{\res}{$res$\xspace}
\newcommand{\tab}{\hspace*{7mm}}

\newcommandx{\TipoFuncion}[3]{%
  \NombreFuncion{#1}(#2) \ifx#3\empty\else $\to$ \res\,: \TipoVariable{#3}\fi%
}
\newcommand{\In}[2]{\ModificadorArgumento{in} \ensuremath{#1}\,: \TipoVariable{#2}\xspace}
\newcommand{\Out}[2]{\ModificadorArgumento{out} \ensuremath{#1}\,: \TipoVariable{#2}\xspace}
\newcommand{\Inout}[2]{\ModificadorArgumento{in/out} \ensuremath{#1}\,: \TipoVariable{#2}\xspace}
\newcommand{\Aplicar}[2]{\NombreFuncion{#1}(#2)}

\newlength{\IntFuncionLengthA}
\newlength{\IntFuncionLengthB}
\newlength{\IntFuncionLengthC}
%InterfazFuncion(nombre, argumentos, valor retorno, precondicion, postcondicion, complejidad, descripcion, aliasing)
\newcommandx{\InterfazFuncion}[9][4=true,6,7,8,9]{%
  \hangindent=\parindent
  \TipoFuncion{#1}{#2}{#3}\\%
  \textbf{Pre} $\equiv$ \{#4\}\\%
  \textbf{Post} $\equiv$ \{#5\}%
  \ifx#6\empty\else\\\textbf{Complejidad:} #6\fi%
  \ifx#7\empty\else\\\textbf{Descripci\'on:} #7\fi%
  \ifx#8\empty\else\\\textbf{Aliasing:} #8\fi%
  \ifx#9\empty\else\\\textbf{Requiere:} #9\fi%
}

\newenvironment{Descripcion}{%
  \parskip=2ex%
%%  \noindent\textbf{\Large Interfaz}%
  \par%
}{}

\newenvironment{Descripcionbis}{%
  \parskip=2ex%
  \parindent 0em %\textbf{\Large Interfaz}%
  \par%
}{}

\newenvironment{Interfaz}{%
  \parskip=2ex%
  \noindent\textbf{\Large Interfaz}%
  \par%
}{}

\newenvironment{Representacion}{%
  \vspace*{2ex}%
  \noindent\textbf{\Large Representaci\'on}%
  \vspace*{2ex}%
}{}

\newenvironment{Algoritmos}{%
  \vspace*{2ex}%
  \noindent\textbf{\Large Algoritmos}%
  \vspace*{2ex}%
}{}


\newcommand{\Titulo}[1]{
  \vspace*{1ex}\par\noindent\textbf{\large #1}\par
}

\newenvironmentx{Estructura}[2][2={estr}]{%
  \par\vspace*{2ex}%
  \TipoVariable{#1} \textbf{se representa con} \TipoVariable{#2}%
  \par\vspace*{1ex}%
}{%
  \par\vspace*{2ex}%
}%

\newboolean{EstructuraHayItems}
\newlength{\lenTupla}
\newenvironmentx{Tupla}[1][1={estr}]{%
    \settowidth{\lenTupla}{\hspace*{3mm}donde \TipoVariable{#1} es \TipoVariable{tupla}$($}%
    \addtolength{\lenTupla}{\parindent}%
    \hspace*{3mm}donde \TipoVariable{#1} es \TipoVariable{tupla}$($%
    \begin{minipage}[t]{\linewidth-\lenTupla}%
    \setboolean{EstructuraHayItems}{false}%
}{%
    $)$%
    \end{minipage}
}

\newcommandx{\tupItem}[3][1={\ }]{%
    %\hspace*{3mm}%
    \ifthenelse{\boolean{EstructuraHayItems}}{%
        ,#1%
    }{}%
    \emph{#2}: \TipoVariable{#3}%
    \setboolean{EstructuraHayItems}{true}%
}

\newcommandx{\RepFc}[3][1={estr},2={e}]{%
  \tadOperacion{Rep}{#1}{bool}{}%
  \tadAxioma{Rep($#2$)}{#3}%
}%

\newcommandx{\Rep}[3][1={estr},2={e}]{%
  \tadOperacion{Rep}{#1}{bool}{}%
  \tadAxioma{Rep($#2$)}{true \ssi #3}%
}%

\newcommandx{\RepFuncion}[6][]{
  \tadOperacion{#1}{#2}{#3}{#4}
  \tadAxioma{#1(#5)}{#6}
}%


\newcommandx{\Abs}[5][1={estr},3={e}]{%
  \tadOperacion{Abs}{#1/#3}{#2}{Rep($#3$)}%
  \settominwidth{\hangindent}{Abs($#3$) \igobs #4: #2 $\mid$ }%
  \addtolength{\hangindent}{\parindent}%
  Abs($#3$) \igobs #4: #2 $\mid$ #5%
}%

\newcommandx{\AbsFc}[4][1={estr},3={e}]{%
  \tadOperacion{Abs}{#1/#3}{#2}{Rep($#3$)}%
  \tadAxioma{Abs($#3$)}{#4}%
}%

\usepackage{hyperref}
\newcommand{\DRef}{\ensuremath{\rightarrow}}

\usepackage{caratula}
\sloppy
\hypersetup{%
 % Para que el PDF se abra a p\'agina completa.
 pdfstartview= {FitH \hypercalcbp{\paperheight-\topmargin-1in-\headheight}},
 pdfauthor={C\'atedra de Algoritmos y Estructuras de Datos II - DC - UBA},
 pdfkeywords={TADs b\'asicos},
 pdfsubject={Tipos abstractos de datos b\'asicos}
}

\parskip=5pt % 10pt es el tamaño de fuente

% Pongo en 0 la distancia extra entre ítemes.
\let\olditemize\itemize
\def\itemize{\olditemize\itemsep=0pt}

\materia{Algoritmos y Estructuras de datos II }

\titulo{Trabajo Pr\'actico 2}
\grupo{Grupo 21}
\integrante{Lizana, Helen}{118/08}{hsle.22@gmail.com}
\integrante{Romero, Nicol\'as Dami\'an }{779/07}{nico.romerocuruchet@gmail.com}
\integrante{Martinez, Ignacio}{438/09}{ignaciomartinez88@hotmail.com}
\integrante{Casalla, Dante}{83/11}{dante244@hotmail.com}


\begin{document}
\maketitle 
\section{M\'odulo Wolfie}
\setlength{\parindent}{0pt}
\begin{Interfaz}
\noindent
\textbf{Usa}: Cliente, T\'itulo, Promesa, Nat, Conj($\alpha$)\\
  \textbf{Se explica con}: \tadNombre{Wolfie}\\
  \textbf{G\'eneros}: \TipoVariable{wolfie}\\
  \textbf{Operaciones}:

  \InterfazFuncion{inagurarWolfie}{\In{cs}{conj(cliente)}}{wolfie}%
  [$\neg \emptyset $?($cs$)]
  {$res \igobs$ inagurarWolfie(cs)}%
  [O($\#(cs)^2$)]
  [Ignaura wolfie con el conjunto de clientes $cs$.]
  [$cs$ se almacena en la estructura del wolfie]

  \InterfazFuncion{agregarTitulo}{\In{t}{t\'itulo}, \Inout{s}{wolfie}}{}
  [$w \igobs w_0$ $\land$ $t \notin$ t\'itulos($w_{0}$) ]
  {$w \igobs$ agregarTitulo(t,$w_0$)}%
  [O($|nombre(t)| + \#clientes(w)$)]
  [Agrega el t\'itulo $t$ a los t\'itulos del wolfie.]
   
  \InterfazFuncion{actualizarCotizacion}{\In{nt}{nombre},\In{cot}{nat}, \Inout{w}{wolfie}}{}
  [$w \igobs w_0$ $\land$ $\exists$ $t \in$ t\'itulos($w_0$) $| nombre(t) = nt$]
  { w $\igobs$ actualizarCotizacion(nt, cot, $w_0$)}%
  [O($C * |nombre(nt)| + C*log(C)$), donde C es $\#clientes(w)$]
  [Cambia la cotizaci\'on del t\'itulo $nt$ perteneciente a t\'itulos($w$).]

   \InterfazFuncion{agregarPromesa}{\In{c}{cliente},\In{p}{promesa}, \Inout{w}{wolfie}}{}
  [$w \igobs w_0$ $\land$ $c \in$ clientes($w_0$) $\land$ ($\exists$ t:t\'itulo)(t $\in$ t\'itulos($w_0$) $\Rightarrow$ nombre(t) $\igobs$ nombre(t\'itulo(p))) \\
  $\land$ ($\forall p_2$: promesa)($p_2 \in$ promesasDe(c, $w_0$) $\Rightarrow$ (t\'itulo(p) $\neq$ t\'itulo($p_2$) $\lor$ tipo(p) $\neq$ tipo($p_2$)) $\land$ \\
  (tipo(p) = vender $\Rightarrow$ accionesPorCliente(c, t\'itulo(p), $w_0$) $\geq$ cantidad(p)))]
  { w $\igobs$ agregarPromesa(c, p,$w_0$) }
  [|nombre(t\'itulo(p))| + log(C)]
  [Agrega la promesa $p$ para el cliente $c$.]
  
  \InterfazFuncion{clientes}{\In{w}{wolfie}}{itConj(cliente)}
  [true]
  {$res \igobs$ crearIt(clientes($w$))}%
  [O(1)]
  [Devuelve un iterador al conjunto de cliente de wolfie $w$.]
  [no se puede modificar $res$.]
    
  \InterfazFuncion{t\'itulos}{\In{w}{wolfie}}{itConj(t\'itulo)}
  [true]
  {$res \igobs$ crearIt(t\'itulos($w$))}%
  [O(1)]
  [Devuelve un iterador al conjunto de t\'itulos de wolfie $w$.]  
  [no se puede modificar $res$.]
  
  \InterfazFuncion{promesasDe}{\In{c}{cliente},\In{w}{wolfie}}{itConj(promesa)}
  [$c \in$ clientes($w$)]
  {$res \igobs$ crearIt(PromesasDe($c$, $w$))}%
  [O(1) para llamadas consecutivas con el mismo cliente, y O$(T*C*|max\_nt|)$ \\donde T es $\#$(t\'itulos(w)), 
  C es $\#(clientes(w))$ y nt es la longitud maxima de los nombres de los \\titulos de w]
  [Devuelve todos las promesas de $c$.]
  [no se puede modificar $res$.]
\newpage
  \InterfazFuncion{accionesPorClientes}{\In{c}{cliente},\In{nt}{nombre}, \In{w}{wolfie}}{nat}
  [$c \in$ cliente($w$) $\land$ $\exists t \in titulos(w) |$ nombre(t) =nt]
  {$res \igobs$ accionesPorClientes($c$, $nt$, $w$)}%
  [O(log(C) + $|nt|$)]
  [Devuelve la cantidad de acciones que posee del titulo de nombre $nt$.]
 
  \InterfazFuncion{enAlza}{\In{nt}{t\'itulo}, \In{w}{wolfie}}{bool}
  [$\exists t \in titulos(w) |$ nombre(t) =nt]
  {$res \igobs$ enAlza($nt$, $w$)}%
  [O$(|nt|)$]
  [Devuelve verdadero si el t\'itulo esta en alza.]

  
\end{Interfaz}


\begin{Representacion}
  
  \Titulo{Representaci\'on de wolfie}

  \begin{Estructura}{wolfie}[str]
    \begin{Tupla}[str]
    \tupItem{accionesPorCliente}{dicc\_a(cliente,tupla(dicc\_t(t: nombre, cantAcciones: nat), accTotales: nat)}\\
    \tupItem{PromesasPorT\'itulo}{dicc\_t(t:nombre, tupla(lv:lista(parpc), \\cc: conj\_h(promCliente), it: itConj(t\'itulo), accDisponibles: nat))} \\
    \tupItem{T\'itulos}{conj(t\'itulo)} \\
    \tupItem{Clientes}{conj(cliente)} \\
    \tupItem{UltimoCliente}{tupla(cliente,conj(promesa), bool)} \\
    \end{Tupla}
    \end{Estructura}
   \noindent promC es tupla(cliente,nat,promesa) y parpc es tupla(promesa, cliente)\\
 
\textbf{Elecci\'on de la estructura str}:\\

Decidimos implementar Wolfie con esta estructura, donde \textit{accionesPorCliente} tendr\'a como claves a los clientes pasados por 
par\'ametro cuando se ignaurar Wolfie; cada significado ser\'a una tupla que contiene la cantidad total de acciones y un diccionario
 que tendra las de acciones por t\'itulo que posea; este diccionario es de g\'enero dicc\_t que estar\'a implementado sobre un
  Trie lo cual har\'a que la complejidad de busqueda del t\'itulo $t$ se de $|nombre(t)|$.\\ 
\textit{PromesasPorT\'itulo} es un diccionario dicc\_t que almacenar\'a los nombres de t\'itulos que se le vaya incorporando al Wolfie, 
y sus significados ser\'an: tupla de lista de promesas de venta, un conjunto de promesas de compra, un iterador de conjunto(t\'itulo) (donde 
el nombre del ``Siguiente'' de ese iterador se corresponde con el nombre de la clave) y un nat que es la cantidad disponible de ese t\'itulo.\\
\textit{PromesasPorT\'itulo} es una tupla(cliente,conj(promesa),bool), el conjunto de la tupla se devolver\'a en  $O(1)$ si el cliente
que se consulta es igual al cliente de la tupla, el booleano indicar\'a si el cliente de la tupla ya hab\'ia sido consultado anteriormente.\\
\textit{T\'itulos} es un conjunto  los t\'itulos del wolfie y 
\textit{Clientes} es el conjunto de clientes del Wolfie.\\
\newpage
	

  \Rep[str][e]{[ \\
  /*Clientes es igual a claves de accionesPorClientes*/ \\
  e.Clientes $\igobs$ claves(e.accionesPorCliente) $\land_{L}$ \\
  
  /*las claves de los significados del accionesPorClientes estan incluidos en claves de PromesasPorTitulo*/ \\
  ($\forall$c:cliente)(def$?$(c, e.accionesPorCliente) $\Rightarrow$ (($\forall$d: dicc\_t(nombre,nat))\\
  (d $=$ $\Pi_{1}$(Obtener(c,accionesPorCliente)) $\Rightarrow_{L}$ claves(d) $\subseteq$  claves(e.PromesasPorTitulo)) $\land_{L}$\\
  /*La suma total de acciones de ese cliente es igual Pi\_2 del obtener e.accionesPorClientes*/\\
  $\Pi_{2}$(Obtener(c, e.accionesPorClientes) = sumaAcciones($\Pi_{1}$(Obtener(c, e.accionesPorClientes))
  
  /*todas las claves de PromesasPorTitulo se corresponden con los nombres de los titulos*/\\
  claves(e.PromesasPorTitulo) $\igobs$ nombres(claves(e.PromesasPorTitulo)) $\land_{L}$\\
  
  /*el cliente de UltimoCliente pertenece a los clientes*/ \\
  $\Pi_{1}(e.UltimoCliente) \in e.Clientes$ $\land_{L}$ \\
  /*y $\Pi_{3}$ de UltimoCliente implica que $\Pi_{2}$ es las promesas del cliente $\Pi_{1}$*/ \\
  ($\neg \Pi_{3}$(e.UltimoCliente) $\land$ $\emptyset ? \Pi_{2}$(e.UltimoCliente)) $\lor$ 
  ($\Pi_{3}$(e.UltimoCliente) $\land$ $\Pi_{2}$(e.UltimoCliente) $\igobs$ buscarPromesas($\Pi_{1}$(e.UltimoCliente), e.PromesasPorT\'itulo)) $\land$\\
  
  /*Para todo titulo, la cantidad total de acciones que tienen los clientes de cada titulo es menor al $\#$m\'axAcciones de ese titulo*/\\
  ($\forall$t:t\'itulo)(t$\in$ e.Titulos $\Rightarrow$ (totalDeAcciones(e.Clientes, nombre(t), e.accionesPorClientes) $\le$ $\#$m\'axAcciones(t)) $\land$\\
  /*y que $\#$m\'axAcciones de ese titulo menos la suma total es igual a la cantidad de accionesDisponible*/\\
  $\#$m\'axAcciones(t) $-$ totalDeAcciones(e.Clientes, nombre(t), e.accionesPorClientes) $=$ $\Pi_{4}$(obtener(nombre(t), e.PromesasPorTitulo)) 
  ) $\land$ \\
  
  /*Las promesas de ventas son v\'alidas*/\\
  ($\forall$ nt: nombre)(def$?$(nt, e.PromesasPorTitulo) $\Rightarrow_{L}$ \\
  sinClientesRepetidos($\Pi_{1}$(Obtener(nt, e.PromesasPorTitulo))) $\land$ \\
  ($\forall$ p:parpc)(esta$?$(p,$\Pi_{1}$(Obtener(nt, e.PromesasPorTitulo))) $\Rightarrow_{L}$ tipo$(\Pi_{1}(p))=VENTA$ $\land$ \\ 
  t\'itulo($\Pi_{1}(p)$) = nt $\land$ $\Pi_{2}(p) \in$ e.accionesPorClientes $\land_{L}$
   cantidad($\Pi_{1}(p)$) $\le$ Obtener(nt, Obtener($\Pi_{2}(p)$, e.accionesPorClientes ))) $\land_{L}$ \\

  /*Las promesas de compras son v\'alidas*/\\
  ($\forall$ p2:promC)(p2 $\in$ $\Pi_{2}$(Obtener(nt, e.PromesasPorTitulo)) $\Rightarrow$ $\Pi_{3}(p2) = COMPRA$ $\land$ \\
  $\Pi_{1}(p2)$ $\in$ e.Clientes $\land_{L}$ $\Pi_{2}(p2)=$ Obtener(nt, Obtener($\Pi_{1}(p2)$, e.accionesPorClientes))) $\land$\\
  
  /*el nombre de Siguiente(it) se corresponde con el nombre de su clave */\\
  nt = Siguiente($\Pi_{3}$(Obtener(nt, e.PromesasPorTitulo))) $\land_{L}$\\
  /*el Siguiente de it es uno de los titulos del conjunto titulos*/\\
  ($\exists$ t: t\'itulo)(t$\in$ e.Titulos $\Rightarrow$ Alias(t $=$ Siguiente($\Pi_{3}$(Obtener(nt, e.PromesasPorTitulo))))
  ))  ]}

 
  \AbsFc[estr]{wolfie}[e]{$ w:wolfie$ $| (clientes(w) = e.Clientes \wedge$ \\
  t\'itulos(w) = e.t\'itulos $\wedge_L (\forall c \in $clientes(w)) \\
  (promesasDe(c,w) = buscarPromesas(c, e.PromesasPorT\'itulo, claves(e.PromesasPorT\'itulo)) \\
  $\wedge$ ($\forall$ nt: nombre) nt $\in$ nombres(t\'itulos(w)) $\Rightarrow$ \\
  (accionesPorClientes(c, nt, w) = obtener(nt, Obtener(c, e.accionesPorCliente)))}
 
\noindent
\textbf{Auxiliares}:

	sDicc es dicc(nombre,tupla(secu(parpc),conj(promC),iterConj,nat))/d, conj(nombre) \\
  \tadOperacion{buscarPromesas}{cliente/c, sDicc/f}{conj($promesa$)}{f $\subseteq$ claves(d)}
  \tadAxioma{buscarPromesas($c$,$d$,$f$)}{\IF $EsVacio?(f)$ THEN $\emptyset$ ELSE 
  damePromV(c,$\Pi_1$(Obtener(DameUno(f),d))) $\cup$ \\ damePromC(c,DameUno(f), $\Pi_2$(Obtener(DameUno(f),d)) $\cup$ \\
  buscarPromesas(c,d,sinUno(f))FI}
  \tadOperacion{damePromV}{cliente/c, secu(parpc)/s }{conj($promesa$)}{}
  \tadAxioma{damePromV($c$, $s$)}{\IF vacia$?$(s) THEN $\emptyset$ ELSE
  {\IF c = $\Pi_{1}$(prim(s)) THEN Ag($\Pi_{2}$(prim(s)), damePromV(c, fin(s))) ELSE  damePromV(c, fin(s)) FI} 
  FI }
  \tadOperacion{damePromC}{cliente/c, conj(promC)/cj }{conj($promesa$)}{}
  \tadAxioma{damePromC($c$, $cj$)}{\IF vacia$?$(s) THEN $\emptyset$ ELSE
  {\IF c = $\Pi_{1}$(DameUno(cj)) THEN Ag($\Pi_{3}$(DameUno(cj)), damePromC(c, sinUno(cj))) ELSE  damePromC(c, sinUno(cj)) FI} 
  FI }
  \tadOperacion{nombres}{conj(t\'itulo)/c }{conj(nombre)}{}
  \tadAxioma{nombres($c$)}{\IF vacia$?$(c) THEN $\emptyset$ ELSE Ag(nombre(DameUno(c)), nombres(sinUno(c))) FI }
  
  \tadOperacion{nombres}{conj(t\'itulo)/c }{conj(nombre)}{}
  \tadAxioma{nombres($c$)}{\IF vacia$?$(c) THEN $\emptyset$ ELSE Ag(nombre(DameUno(c)), nombres(sinUno(c))) FI }
  
  \tadOperacion{sumaAcciones}{dicc\_t(nombre,nat)/d }{nat}{}
  \tadAxioma{sumaAcciones($d$)}{auxSumaAcciones(claves(d), d) }
  
  \tadOperacion{auxSumaAcciones}{conj(nombre)/c, dicc\_t(nombre,nat)/d }{nat}{c $\subseteq$ claves(d)}
  \tadAxioma{auxSumaAcciones($c$,$d$)}{\IF vacia$?$(c) THEN 0
  ELSE Obtener(dameUno(c), d) + auxSumaAcciones(sinUno(c),d) FI }
  
  \tadOperacion{totalDeAcciones}{conj(clientes)/c, nombre/n, dicc\_a(clientes,tupla(dicc\_t(nombre,nat),nat))/d }{nat}{c $\subseteq$ claves(d) 
  $\land$ ($\forall$c:cliente) def$?$(c,d) $\Rightarrow_{L}$ n $\in$ claves($\Pi_{1}$(obtener(c,d)))}
  \tadAxioma{sumaAcciones($c$,$n$,$d$)}{\IF vacia$?$(c) THEN 0
  ELSE Obtener(n, Obtener(dameUno(c),d)) + sumaAcciones(sinUno(c),$n$,$d$) FI }
  
  \tadOperacion{SinClientesRepetidos}{secu(parpc)}{bool}{}
  \tadAxioma{SinClientesRepetidos($s$)}{($\forall$ j,i: parpc)(j$\neq$i $\land$ esta$?$(j,s) $\land$ esta$?$(i,s) $\Rightarrow$ $\Pi_2$(j)$\neq$ $\Pi_{2}$(i)) }
  
  
\end{Representacion}
\newpage
\begin{Algoritmos}


Para el c\'alculo de complejidades temporales consideramos las siguientes variables:\\
  C:	Cardinal del conjunto de clientes de wolfie \\
  T:	Cardinal del conjunto de t\'itulos del wolfie \\
  P:	Cantidad de promesas pendientes del wolfie \\
  |nt|:	longitud del nombre del t\'itulo $nt$ \\
  
\begin{lstlisting}
iInagurarWolfie(in cs:conj(clientes)) -> res:str	//O(C*C)
  
  res.Clientes <- cs					//O(1)
  res.Titulo <- Vacio()					//O(1)
 
  it <- CrearIt(cs)	
  Pi_1(res.UltimoCliente) <- Siguiente(it)		//O(1)
  Pi_2(res.UltimoCliente) <- Vacio()			//O(1)
  Pi_3(res.UltimoCliente) <- false			//O(1)
  res.PromesasPorTitulos <- CrearT()			//O(1)
  
  var ls:lista(tupla(cliente, tupla(dicc_t(nombre,nat),nat)))
  //creo una lista vacia	
  ls <- Vacia()						//O(1)
  
  while(HaySiguiente?(it))				//O(C)

    var t:tupla(cliente, tupla(dicc_t(nombre,nat)))
    t <- tupla(Siguiente(it), tupla(CrearT(),0))	//O(1)
    // CrearT() esta en la interfaz de Trie
    AgregarAdelante(ls,t)				//O(1)
    avanzar(it)						//O(1)

  endWhile
  
  //NuevoD de dicc_a
  res.accionesPorCliente <- NuevoD(ls)			//O(C*C)

\end{lstlisting}

\begin{Descripcionbis}
COMPLEJIDAD TEMPORAL: O($C*C$)\\
Se copia por referencia el conjunto de clientes en O(1). Luego se crean conjuntos y listas vacias en O(1), y por \'ultimo,
nuevoD devuelve un dicc\_a donde las claves son los Pi\_1 de la secuencia pasada por parametro y el significado son los Pi\_2
respectivamente.\\

\end{Descripcionbis}

\begin{lstlisting}
iAgregarTitulo(in t:titulo, in/out e:str)		//O(|nombre(t)| + C)

  var it: itConj(titulo)
  it<- AgregarRapido(e.Titulos,t)			//O(1)

  var s: lista(tupla(cliente, promesa))
  s <-Vacia()						//O(1)
 
  var h: conj_h(tupla(cliente,nat,promesa))
  h<-VacioH(Cardinal(e.Clientes))			//O(C)
  
  p<- tupla(s,h,it, #MaxCantAcciones(t))		//O(1)
  //Definir() esta en la interfaz de trie
  Definir(Nombre(t), p, e.PromesasPorTitulos)		//O(|nombre(t)|)
  							//O(1)
  AgregarRapido(nombre(t), q, e.Titulos)		//O(1)

\end{lstlisting}

\begin{Descripcionbis}
COMPLEJIDAD TEMPORAL: O($|nombre(t)| + C$)\\
\end{Descripcionbis}
\\
\begin{lstlisting}
iActualizarCotizacion(in nt:nombre, in cot:nat, in/out e:str){	//O(C*|nt| + C*log(C))
  
//Actualizo cotizacion del titulo:
//tituloAct: <lista/lv, conj_h/cc, itConj(titulo)/it,nat/accDisponible>

var tituloAct: tupla(lista(parpc), conj_h(prom), itConj(titulo),nat)

//Obtener es una funcion del modulo trie
tituloAct <- Obtener(nt, e.PromesasPorTitulo) 		    //O(|nt|) 				    		    
recotizar(cot, Siguiente(tituloAct.it))			    //O(1)				    		    

//Primero se ejecutan las promesas de venta	
itVenta <- CrearIt(tituloAct.lv))
var tmp: conj(tupla(cliente,nat))

//El ciclo se ejecuta a lo sumo C veces, ya que puede haber una unica promesa de venta
//por cada cliente
while HaySiguiente?(itVenta)				   //O(C*|nt| + C*log(C))

	//el peor caso es cuando se ejecutar todas las promesas de venta
	if(limite(Pi_1(Siguiente(itVenta))) <= cot) then

	  //Obtengo el trie con las acciones del cliente
	  //Obtener() es de Diccionario Arreglo (por referencia)
	  var tr: dicc_t(nombre,nat)
	  tr <- Pi_1(Obtener(Pi_2(Siguiente(itVenta)), e.AccionesPorCliente)) //O(log(C))

	  //Obtener() es de la interfaz de dicc_t
	  f  <- Obtener(nt, tr)				   	     	//O(|nt|)
	  f <- f - limite(Pi_1(Siguiente(itVenta)))			//O(1)
	  //Actualizo las acciones de ese titulo
	  Definir(nt, f,tr)	     //O(|nt|)
		
	  //Actualizo Acc.Disponibles O(1)
	 tituloAct.accDisponibles <- tituloAct.accDisponibles + 
	 cantidad(Pi_1(Siguiente(itVenta)))				

	  EliminarSiguiente(itVenta) 				              //O(1)
	else
	  Avanzar(itVenta)					              //O(1)
	fi	

endWhile

//Se actualiza el orden conj de promesas de compra, para cada cliente. Tengo que saber cual
//es el numero total de acciones que posee y luego insertarlo en el heap O(C*log(C))

it <- crearIt(e.Clientes)   //O(1)

while Cardinal(HaySiguiente?(it))          //O(c*Log(c))

	var aux: tupla(cliente,nat,promesa)
	aux <- Sacar(tituloAct.cc)            				//O(log(C))
	//Actualizo la cantidad de acciones del cliente de esa promesa
	Pi_2(aux) <- (Obtener(Pi_1(aux)).accTotales, e.accionesPorCliente)//O(log(n))
	//Agrego el titulo con la nueva cantidad de acciones		
	Agregar(titulosAct.cc, aux)					//O(log(C))			
	Avanzar(it)							//O(1)

endwhile

//tengo actualizado el conjunto de promesas de compra

var q: conj(tupla(cliente, nat, promesa))
q <- Vacio()         //O(1)
var promC: tupla(cliente, nat, promesa)

//Promesas de compra a ejecutar
//El ciclo se ejecuta a lo sumo C veces, ya que puede haber una unica promesa de compra
//por cada cliente
while Cardinal(Pi_2(tituloAct)) > 0 			//O(C*log(C) + C*|nt|)

	promC <- Sacar(tituloAct.cc)                   //O(log(C))

	//el peor caso es cuando se ejecutan todas las promesas de compra	
	if limite(Pi_3(promC)) >= cot && cantidad(Pi_3(promC)) <= tituloAct.accDisponibles

		//Obtengo el trie t  de acciones del cliente	
		t <- Pi_1(Obtener(Pi_1(promC), e.AccionesPorCliente)) 		//O(log(C))
		n <- Obtener(nombre(Pi_3(promC)), t)	        		//O(|nt|)
		Definir(nt, n + cantidad(Pi_3(promC)),t)        		//O(|nt|)
		//Actualizar Acciones disponibles
		tituloAct.accDisponibles <- tituloAct.accDisponibles - cantidad(Pi_3(promC)) //O(1)
	else
		AgregarRapido(q, promC)						//O(1)		
	fi
endWhile

//vuelvo a reestablecer el invariante, es decir a armar el heap con las promsas de compra que no se puedieron efectuar 

itCompra <- CrearIt(q)
while HaySiguiente?(itCompra)							//O(C*log(c))

	Agregar(tituloAct.cc, Siguiente(itCompra)) 				//O(log(C))
	AvanzarIt(itCompra)							//O(1)
endWhile

\end{lstlisting}

\begin{Descripcionbis}
COMPLEJIDAD TEMPORAL: O($C*|nt| + C*log(C)$)\\
\end{Descripcionbis}
\\
\begin{lstlisting}

iAgregarPromesa(in c:cliente, in p:promesa, in/out e:str){	//O(|titulo(p)| + log(C))

	if tipo(p) = VENTA then

		//Obtener esta en la interfaz de modulo trie
		s <- Obtener(Nombre(p), e.PromesasPorTitulo)	     //O(|titulo(p)|)
		//agrega en la lista de las promesas de venta
		AgregarAtras(s.lv, p)				     //O(1)

	else

		//Obtener del Modulo trie
		s <- Obtener(titulo(p), e.PromesasPorTitulo)	     //O(|titulo(p)|)

		n <- (Obtener(c,e.accionesPorCliente)).accTotales   //O(log(C))
		//n indica el numero de acciones que tiene el cliente
		q <- tupla(c, n, p)				     //O(1)
		// Agregar pertenece a la interfaz de Conj_H
		// Cuando se agrega el elemento al conj_h el
		// criterio de orden se hace a traves de la
		// cantidad de acciones totales que posee el cliente 
		Agregar(s.cc, q)				     //O(log(C))

	fi

\end{lstlisting}

\begin{Descripcionbis}
COMPLEJIDAD TEMPORAL: O($|titulo(p)| + log(C)$)\\
La complejidad de Agregar de Conj\_h en el peor caso es de $C + log(C)$, pero como
no puede haber m\'as de una promesa de compra/venta por cliente, la complejidad siempre ser\'a
$log(C)$. Ver en la interfaz de Conj\_h.\\
\end{Descripcionbis}

\begin{lstlisting}
iClientes(in e:str) -> res: itConj(cliente) //O(1)
  res <- crearIt(e.Clientes)		    //O(1)
}
\end{lstlisting}
\begin{Descripcionbis}
COMPLEJIDAD TEMPORAL: O($1$)\\

\end{Descripcionbis}

\begin{lstlisting}
iTitulos(in e:str)->res: itConj(titulos){   //O(1)
  res <- crearIt(e.Titulos)                 //O(1)
}
\end{lstlisting}
\begin{Descripcionbis}
COMPLEJIDAD TEMPORAL: O($1$)\\
\end{Descripcionbis}
\\
\begin{lstlisting}
iAccionesPorClientes(in c:cliente, in nt:nombre, in e:str) -> res: nat //O(log(C) + |nt|)
 

	var d: dicc_t(nombre,cantAcciones) 
	d <- Pi_1(Obtener(c, e.AccionesPorCliente) //O(log(C))
	//Obtener en el modulo trie
	n <- Obtener(nt, d)			   //O(|nt|)
	res <- n			 	   //O(1)

\end{lstlisting}
\begin{Descripcionbis}
COMPLEJIDAD TEMPORAL: O($log(C) + |nt|$)\\
\end{Descripcionbis}
\\
\begin{lstlisting}
iEnAlza(in nt: nombre, in e:str) -> res: bool //O(|nt|)
  
	d <- Obtener(nt, e.PromesasPorTitulos)		//O(|nt|)
	res <- EnAlza(Siguiente(Pi_3(d)))		//O(1)

\end{lstlisting}
\begin{Descripcionbis}
COMPLEJIDAD TEMPORAL: O($|nt|$)\\
\end{Descripcionbis}
\\
\begin{lstlisting}
iPromesasDe(in c:cliente, in/out e:str)-> res:itConj(promesa)
//Complejidad: O(T*C + T*|max_nt|) < O(T*C*|max_nt|)
	
	if Pi_3(e.UltimoCliente) and Pi_1(e.UltimoCliente) = c		//O(1) 

		res <- crearIt(Pi_2(e.UltimoCliente))			//O(1)

	else

		Pi_2(e.UltimoCliente) <- Vacio()			//O(1)
		Pi_1(e.UltimoCliente) <- c				//O(1)
		Pi_1(e.UltimoCliente) <- True				//O(1)
		it <- crearIt(e.Titulos)

		//it itera sobre todos los titulos del wolfie
		while(HaySiguiente?(it))				//O(T)

			t <- Obtener(nombre(Siguiente(it)), e.PromesasPorTitulo)//O(|max_nt|)
			if tienePromesaV(c, Pi_1(t)) then			//O(C)
				p1 <- DamePromesaV(c, Pi_1(t))			//O(C)
				AgregarRapido(Pi_2(e.UltimoCliente), p1)	//O(1)
			fi
			if tienePromesaC(c, Pi_2) then
				p2 <- DamePromesaC(c, Pi_2(t))			//O(C)
				AgregarRapido(Pi_2(e.UltimoCliente), p2)	//O(1)
			fi
			Avanzar(it)					//O(1)
	 	endWhile

	 res <- crearIt(Pi_2(e.UltimoCliente))				//O(1)
fi

\end{lstlisting}

\begin{Descripcionbis}
COMPLEJIDAD TEMPORAL: O($T*C*|max_nt|$)\\
DamePromesaC y DamePromesaV devuelve la promesa por referencia.\\\
\end{Descripcionbis}

\textbf{Funciones Auxiliares:}\\


\begin{lstlisting}
tienePromesaV(in c:cliente, in lv:lista(parpc)) -> res:bool{		//O(long(lv))

		listaIt it <- crearIt(lv)
		res <- false

		while(HaySiguiente?(it) && !res){			//O(long(lv))
			res <- Pi_2(Siguiente(it)) == c			//O(1)
			Avanzar(it)
		}end while
}
\end{lstlisting}
\begin{Descripcionbis}
COMPLEJIDAD TEMPORAL: O(long(lv))) = O(C), dado que la lista tiene a lo sumo C elementos\\
\end{Descripcionbis}

\begin{lstlisting}
tienePromesaC(in c:cliente, in h :conj_h) -> res:bool{			//O(cardinal(h))

		listaIt it <- dameElementos(h)				//O(cardinal(h))
		res <- false

		while(HaySiguiente?(it) && !res){			//O(cardinal(h))
			res <- Pi_1(Siguiente(it)) == c
			Avanzar(it)
		}end while
}
\end{lstlisting}
\begin{Descripcionbis}
COMPLEJIDAD TEMPORAL: O(cardinal(h)) = O(C), dado que el conjunto contiene a los sumo C elementos\\
\end{Descripcionbis}


\begin{lstlisting}
DamePromesaV(in c:cliente, in lv:lista(parpc)) -> res:promesa		//O(long(lv))

		listaIt it <- crearIt(lv)
		
		while(HaySiguiente?(it)){				//O(long(lv))

			if(Pi_2(Siguiente(it)) == c)
				res <- Pi_1(Siguiente(it))

			Avanzar(it)
		}end while
}
\end{lstlisting}
\begin{Descripcionbis}
COMPLEJIDAD TEMPORAL: O(long(lv))) = O(C), dado que la lista tiene a lo sumo C elementos\\\\
Devuelve la promesa por referencia.\\\\
\end{Descripcionbis}


\begin{lstlisting}
DamePromesaC(in c:cliente, in h:conj_h)) -> res:promesa{		//O(cardinal(h))

		listaIt it <- dameElementos(h)  	                //O(cardinal(h))

		while(HaySiguiente?(it)){				//O(cardinal(h))

			if(Pi_1(Siguiente(it)) == c)			//O(1)
				res <- Pi_3(Siguiente(it))

			Avanzar(it)
		}end while
}
\end{lstlisting}
\begin{Descripcionbis}
COMPLEJIDAD TEMPORAL: O(cardinal(h)) = O(C), dado que el conjunto contiene a los sumo C elementos\\\\
Devuelve la promesa por referencia.\\\\
\end{Descripcionbis}


\end{Algoritmos}
%%%%%%%%%%%%%%%%%%Modulo
\section{M\'odulo Promesa}
\setlength{\parindent}{0pt}
\begin{Interfaz}
\noindent
\textbf{Usa}: Nombre, TipoPromesa, Dinero, Nat\\
  \textbf{Se explica con}: \tadNombre{Promesa}\\
  \textbf{G\'eneros}: \TipoVariable{promesa}\\
  \textbf{Operaciones}:

  \InterfazFuncion{crearPromesa}{\In{n}{nombre}, \In{t}{tipoPromesa}, \In{c}{nat}}{promesa}%
  [$c \geq 0$)]
  {$res \igobs$ crearPromesa(n, t, c)}%
  [O($1$)]
  [Crea la promesa del tipo $t$, con nombre $n$ y cantidad $c$.]
  
  \InterfazFuncion{t\'itulo}{\In{p}{promesa}}{nombre}%
  [True]
  {$res \igobs$ nombre(p)}%
  [O($1$)]
  [Devuelve el nombre del t\'itulo de la promesa.]
  
  \InterfazFuncion{tipo}{\In{p}{promesa}}{tipoPromesa}%
  [True]
  {$res \igobs$ tipo(p)}%
  [O($1$)]
  [Devuelve el tipo de la promesa.]
  
  \InterfazFuncion{l\'imite}{\In{p}{promesa}}{dinero}%
  [True]
  {$res \igobs$ l\'imite(p)}%
  [O($1$)]
  [Devuelve el dinero de la promesa.]
  
  \InterfazFuncion{cantidad}{\In{p}{promesa}}{nat}%
  [True]
  {$res \igobs$ cantidad(p)}%
  [O($1$)]
  [Devuelve la cantidad de acciones prometidas promesa.]
  
\end{Interfaz}

\begin{Representacion}

\Titulo{Representaci\'on de promesa}

\begin{Estructura}{promesa}[str]
\begin{Tupla}[str]
\tupItem{titulo}{nombre} 
\tupItem{tipo}{tipopromesa} 
\tupItem{limite}{dinero} 
\tupItem{cantidad}{nat} 
\end{Tupla}
\end{Estructura}	

\Rep[str][e]{True}

\AbsFc[str]{promesa}[e]{e: promesa $| (titulo(e) = e.titulo \wedge$ 
$ tipo(e) = e.tipo \wedge limite(e) = e.limite \wedge cantidad(e) = e.cantidad)$}
 
\end{Representacion}
\begin{Algoritmos}
\begin{lstlisting}
iCrearPromesa(in n:nombre, in t: tipopromesa, in d:dinero, in c:nat) -> res:str{//O(1)
  res.titulo <- n				//O(1)
  res.tipo <- t					//O(1)
  res.limite <- d				//O(1)
  res.cantidad <- c				//O(1)
}

\end{lstlisting}
\begin{Descripcionbis}
COMPLEJIDAD TEMPORAL: O($1$)\\
\end{Descripcionbis}

\begin{lstlisting}
iTitulo(in e:str) -> res:nombre{		//O(1)
  res <- e.titulo				//O(1)
}
\end{lstlisting}
\begin{Descripcionbis}
COMPLEJIDAD TEMPORAL: O($1$)\\
\end{Descripcionbis}

\begin{lstlisting}
iTipo(in e:str) -> res:tipopromesa{		//O(1)
  res <- e.tipo					//O(1)
}
\end{lstlisting}
\begin{Descripcionbis}
COMPLEJIDAD TEMPORAL: O($1$)\\
\end{Descripcionbis}

\begin{lstlisting}
iLimite(in e:str) -> res:dinero{		//O(1)
  res <- e.limite				//O(1)
}
\end{lstlisting}
\begin{Descripcionbis}
COMPLEJIDAD TEMPORAL: O($1$)\\
\end{Descripcionbis}

\begin{lstlisting}
iCantidad(in e:str) -> res:bol{			//O(1)
  res <- e.cantidad				//O(1)
}
\end{lstlisting}
\begin{Descripcionbis}
COMPLEJIDAD TEMPORAL: O($1$)\\
\end{Descripcionbis}


\end{Algoritmos}
\input{titulo.tex}
\input{modDiccArreglo.tex}
\input{diccTrie.tex}
\input{Conj_Heap.tex}
\end{document}

